#include "local_search_key_path.hh"
#include "graph.hh"
#include "utilis.hh"
#include <stdio.h>


list<Path*> * Xp(PathMatrix * PM, Path * p) {

	list<Path*> * l_paths = new list<Path*>();

	// Calculo de V/Xp
	for(int i=0; i<PM->sizeP; i++) {
		for(int j=i; j<PM->sizeP; j++) {
			if((PM->Contains(p, i, j))) {
				for (list<Path*>::iterator it=PM->P[i][j]->begin(); it != PM->P[i][j]->end(); ++it) {
					l_paths->push_front(*it);
				}
			}
		}
	}

	return l_paths;
}

int LocalSearchKeyPath(Graph * G_problem, Graph *& G_sol, PathMatrix *& P_sol) {

	Graph * H = new Graph(G_problem);
	bool need_update = true;
	Path * p , * p_techo;
	int u, v;
	list<Path*> * Lp;
	list<Path *> * l_paths;
	list<Path*> * key_path_list;

	//cout << "1111111111111111111111" << endl;

	while (need_update) {

		need_update = false;
		//cout << "222222222222222222" << endl;
		key_path_list = G_sol->KeyPathDescomposition();
		//cout << "33333333333333333333" << endl;

		//cout << "key_path_list //////////////////////////////////////////" <<endl;
		//PrintListPath(key_path_list); cout << endl;

		while (!need_update && !key_path_list->empty()) {

			p = SelectRandom(key_path_list); // Selecciona y borra de la lista
			//cout << "44444444444444444" << endl;
			u = p->path->front(); v = p->path->back();

			//cout << "P_sol/////////////////////////////////////////////////" <<endl;
			//PrintPathMatrix(P_sol); cout << endl;

			//cout << "G_sol /////////////////////////////////////////////////" <<endl;
			//PrintPartialGraph(G_sol); cout << endl;

			//cout << "p /////////////////////////////////////////////////" <<endl;
			//PrintPath(p); cout << endl;

			// Esto aca es un buen pire para no sumar orden en restablecimeintos, ademas de resolver otros probelmas
			// que habian (mietras calulo C arreglo lo que rimpi, no sumo orden)
			G_sol->SubstractWithoutExtremes(p); // es necesario quitar p a G_sol para recalcular C
			for(int i = 0; i < G_problem->sizeG; i++) {
				H->actived_node[i] = G_problem->actived_node[i];

				if(G_sol->actived_node[i])
					H->W[i] = 0;
				else
					H->W[i] = G_problem->W[i];

				for(int j = i; j < G_problem->sizeG; j++) {
					H->E[i][j] = G_problem->E[i][j];
					if (G_sol->actived_node[i] && G_sol->actived_node[j] && G_sol->E[i][j])
						H->C[i][j] = 0;
					else
						H->C[i][j] = G_problem->C[i][j];
				}
			}
			//cout << "555555555555555555" << endl;

			l_paths =  Xp(P_sol, p);
			H->Substract(l_paths); // H = G/Xp
			H->Add(p); // H = p U (G/Xp)
			l_paths->clear();
			delete l_paths;
			//cout << "H->GetKPathsBetween(u, v, 1, p->Diameter() BEGIN" << endl;
			p_techo = p;

			Lp = H->GetKPathsBetween(u, v, 1, p->Length()-1); // busco un solo camino con diametro menor igual al largo del camino que quite
			if(!Lp->empty()) {
				p_techo = Lp->front();
			}

			//cout << "H->GetKPathsBetween(u, v, 1, p->Length() END" << endl;

			if(H->CostPath(p_techo) <= G_problem->CostPath(p)) {

				//cout << "p_techo ////////////////////////////////////////////////////" <<endl;
				//PrintPath(p_techo); cout << endl;

				//cout << "888888888888888888888888888" << endl;
				G_sol->Add(p_techo);
				P_sol->Update(p, p_techo);

				//cout << "9999999999999999999999" << endl;
				for (list<int>::iterator it=p_techo->path->begin(); it != p_techo->path->end(); ++it) {
					if((*it)!=u && (*it)!=v && G_sol->GetNodeGrade(*it) > 2) {
						need_update = true;
						//cout << "ACTULIZA!!!!!!!!!" << endl;

						//int entero;
						//cin >> entero;
					}
				}
			}
			else
				G_sol->Add(p);

			DeleteListPath(Lp);
			delete p;
		}
	 	DeleteListPath(key_path_list);

	}
	delete H;

	return 0;
}
